package com.xj.algorithm.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * 字符串中的第一个唯一字符
 */
public class L387_字符串中的第一个唯一字符 {

    /**
     * 给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。
     * <p>
     * 案例:
     * <p>
     * s = "leetcode"
     * 返回 0.
     * <p>
     * s = "loveleetcode",
     * 返回 2.
     *  
     * <p>
     * 注意事项：您可以假定该字符串只包含小写字母。
     */
    public static void main(String[] args) {
        System.out.println(firstUniqCharOffice("leetcode"));
        System.out.println(firstUniqCharOffice("loveleetcode"));
        System.out.println(firstUniqCharOffice(""));
    }

    //自己的解法：map和位置指针
    public static int firstUniqChar(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int location = 0;

        int len = s.length();
        if(len==0){
            return -1;
        }
        for (int i = 0; i < len; i++) {
            Integer count = map.get(s.charAt(i));
            if (count == null) {
                map.put(s.charAt(i), 1);
            } else {
                map.put(s.charAt(i), ++count);

                //当前字母重复了，判断是否需要移动下标
                if (s.charAt(i) == s.charAt(location)) {
                    do {
                        location++;
                        if(location>=len){
                            return -1;
                        }
                    } while (map.get(s.charAt(location)) != null && map.get(s.charAt(location)) > 1);
                }
            }

        }
        return location;
    }

    //官方解法：两次遍历，统计个数后，再遍历一遍找数量=1
    public static int firstUniqCharOffice(String s) {
        HashMap<Character, Integer> count = new HashMap<Character, Integer>();
        int n = s.length();

        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            count.put(c, count.getOrDefault(c, 0) + 1);
        }

        for (int i = 0; i < n; i++) {
            if (count.get(s.charAt(i)) == 1)
                return i;
        }
        return -1;
    }
}
